/**
 * 
 */
package implementations;

import interfaces.Edge;
import interfaces.Vertex;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import sun.reflect.generics.reflectiveObjects.NotImplementedException;

/**
 * @author Kai Bielenberg (kai.bielenberg@haw-hamburg.de)
 *
 */
public abstract class AbstractDirectedGraph<E, V> extends AbstractGraph<E, V> {
    @Override
    public String traverse() { // Ausgabe Graph
        Vertex<V> v= edges().iterator().next().start();
        return traverse_(v, new HashSet<Edge<E,V>>(this.edges()), calcStartIncidenceList(),0);
    }
    
    protected String traverse_(Vertex<V> v, Set<Edge<E,V>> s, Map<Vertex<V>, Set<Edge<E,V>>> i, int indent) {
        String result = "";
        String space="";
        // Leerzeichen zum Einruecken wenn neuer Weg gegangen wird. Je nach Verschachtelungstiefe wird dann weiter eingerueckt.
        for(int n=0; n<indent;n++){ space+="      ";}
        result += v + "\n";
        for(Edge<E,V> e: i.get(v)){
                if(s.remove(e)){
                        result += (" " + space+"-"+e+"-");
                        // Sonderfall Schleife: Hier muss die Verschachtelungstiefe um einen zur�ckgesetzt werden, daher indent -=1;
                        if(v.equals(e.otherVertex(v))){ indent-=1;}
                        if(i.containsKey(e.end())) {
                        result += traverse_(e.otherVertex(v), s, i, indent+1);
                        }
                        else {
                            result += e.end() + "\n";  
                        }
                }
        }
      if(!s.isEmpty()) result += traverse_(s.iterator().next().start(), s, i, 0);
        return result;
}

    public boolean isDirected() {
        
        return true;
    }
    
	@Override
	public boolean hasEulerTour(){
		boolean result=true;
		Map<Vertex<V>, Set<Edge<E, V>>> startIncidenceList = calcStartIncidenceList();
		Map<Vertex<V>, Set<Edge<E, V>>> endIncidenceList = calcEndIncidenceList();
		Iterator<Vertex<V>> iterator = vertices().iterator();
		while(result && iterator.hasNext()){
			Vertex<V> v=iterator.next();
			if (startIncidenceList.get(v).size() != endIncidenceList.get(v).size()) result = false;
		}
		return result;
	}
	
}
